import java.util.ArrayList;
import java.util.Arrays;

/**
* @description: 792. 匹配子序列的单词数
* @author hewei
* @date 2022/8/26 15:33
* @version 1.0
*/

public class NumMatchingSubseq {

    public static void main(String[] args) {
        NumMatchingSubseq numMatchingSubseq = new NumMatchingSubseq();
        String[] words ={"a","bb","acd","ace"};
        System.out.println(numMatchingSubseq.numMatchingSubseq("abcde", words));
    }

    public int numMatchingSubseq1(String s, String[] words) {
        ArrayList<Integer>[] nums = new ArrayList[26];
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            if (nums[c] == null) nums[c] = new ArrayList<>();
            nums[c].add(i);
        }
        int ans = 0;
        for (String word : words) {
            int[] temp = new int[26];
            Arrays.fill(temp, -1);
            int last = -1;
            boolean flag = true;
            for (int i = 0; i < word.length(); i++) {
                int index = word.charAt(i) - 'a';
                if (nums[index] == null || nums[index].size() == temp[index] + 1 || nums[index].get(nums[index].size() - 1) <= last) {
                    flag = false;
                    break;
                }
                ArrayList<Integer> list = nums[index];
                int l = temp[index] + 1;
                int r = list.size() - 1;
                while (l < r) {
                    int mid = (r - l) / 2 + l;
                    if (list.get(mid) <= last) {
                        l = mid + 1;
                    } else r = mid;
                }
                last = list.get(l);
                temp[index] = l;
            }
            if (flag) ++ans;
        }
        return ans;
    }

    public int numMatchingSubseq(String s, String[] words) {
        ArrayList<String>[] nums = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            nums[i] = new ArrayList<>();
        }
        for (String word : words) {
            nums[word.charAt(0) - 'a'].add(word);
        }
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            ArrayList<String> list = nums[index];
            nums[index] = new ArrayList<>();
            for (String temp : list) {
                if (temp.length() > 1) {
                    int a = temp.charAt(1) - 'a';
                    nums[a].add(temp.substring(1));
                } else ++ans;
            }
        }
        return ans;
    }
}
